Programming languages that have built-in thread generating capability, for example JAVA and C# (C sharp), typically include a synchronization mechanism for coordinating thread access to an object. As will be appreciated by those of ordinary skill in the art, the term “thread” refers to a series of processor instructions running on behalf of a user or process, and is logically represented as one or more executing objects. An object is an instance of a class, where a class is a collection of data and methods to operate on the data. In the case of multiple threads of execution, care must be taken to prevent the multiple threads from modifying the same object simultaneously in a way that might leave the object's state corrupted. In particular, there may be critical sections of code or entire methods that must not be executed simultaneously by two or more threads. Thus, multithreaded systems typically provide specialized statements to protect these critical sections.
For example, JAVA provides the synchronized statement to protect critical sections of code from being executed simultaneously. Use of the synchronized statement enables acquisition of an exclusive lock of an object identified by the synchronized statement. Thus, a thread is not able to execute a critical section of code until it can obtain an exclusive lock on the corresponding object and once such a lock is obtained, no other thread can access the critical section of code. This protocol ensures that multiple threads cannot execute the critical section at the same time. Of course, application of the synchronized statement is generally used in cases where a particular program creates multiple threads to share data. If only one thread ever accesses a data structure, there is no need to protect it with a synchronized statement.
A synchronized statement in JAVA source code is normally converted to instructions in JAVA virtual machine (JVM) language, because, as is known in the art, JAVA source code is first compiled into bytecode (i.e., JVM language) prior to being interpreted into machine code by the JVM. A monitorenter instruction is provided in JVM language to gain an exclusive lock on an object. A monitorexit instruction is provided in JVM language to unlock the exclusive lock on the object. Accordingly, if a thread successfully executes the monitorenter instruction upon an object, that thread is considered to have gained temporary exclusive lock ownership of the object (i.e., it has gained a “lock” on the object to prevent other threads from accessing the critical sections of code). To signify that ownership, the thread's identifier appears in a specialized field associated with the object, for example, a “LockOwner” field in the object. If another thread, or second thread, attempts to execute the monitorenter instruction upon the same object, while the first thread has temporary exclusive ownership of the object, the second thread must wait (i.e., sleep) until the first thread (i.e., current lock owner) executes the monitorexit instruction to release its exclusive lock of the object.
The monitorenter instruction for a lock operation typically includes at least two steps. The first step, (referred to herein as the “checking” step), occurs when a thread attempting to gain an exclusive lock on a particular object checks a shared flag of the object. The shared flag indicates whether the object is currently locked by another thread. If the shared flag indicates that no other thread has an exclusive lock on the object (e.g., the shared flag indicates NULL), the thread attempting to gain the exclusive lock is free to perform the second step of “labeling” the object to claim lock ownership of the object. Labeling the object may be accomplished in any number of ways. For example, the shared flag may be altered to reflect the thread's identifier (e.g., a Thread_ID or a start address of the thread's runtime stack). Once labeled with that thread's identifier, the object is temporarily unavailable for locking by other threads.
However, in order for the monitorenter instruction to be effective, atomic execution of both of the lock operation steps is required to prevent possible race conditions from occurring (i.e., the labeling step must be performed immediately after the checking step by the same thread, and the two steps operate like one indivisible step.). If not atomically executed, a second thread may be able to interleave itself into the first thread's lock attempt by performing the checking step and erroneously determining that the object is available to be locked immediately after the first thread has performed the checking step. In other words, the second thread may be able to sneak-in before the first thread is able to complete the labeling step necessary to gain an exclusive lock on the object. Thus, atomic execution of the two lock operation steps prevents two threads from concurrently modifying data in a locked region represented by the same object, thereby precluding possible data corruption.
Although safe, prior art atomic execution of lock operation steps is expensive in terms of processor clock cycles. For example, the cycles spent in the execution of an atomic lock operation is, in some instances, equivalent to that of many other instructions, (e.g., execution of a few hundred add instructions).